using System;
using System.Collections.Generic;

namespace PathX.Collection
{
    /// <summary>Represents a Heap data structure.</summary>
    /// <typeparam name="T">The item type</typeparam>
    public abstract class BinaryHeapBase<T>
    {
        private int _used;
        private T[] _heap;
        private IComparer<T> _comparer;

        /// <summary>
        /// Initializes a new instance of the class.
        /// </summary>
        /// <param name="capacity">The capacity.</param>
        /// <param name="comparer">The comparer used to compare the item in the heap.</param>
        protected BinaryHeapBase(int capacity, IComparer<T> comparer)
        {
            if (capacity < 4)
                capacity = 4;
            this._heap = new T[capacity];
            this._comparer = comparer;
        }

        /// <summary>Gets the count.</summary>
        /// <value>The count.</value>
        public int count => this._used;

        /// <summary>Gets the capacity.</summary>
        /// <value>The capacity.</value>
        public int capacity => this._heap.Length;

        /// <summary>
        /// Gets a value indicating whether this instance has any items.
        /// </summary>
        /// <value>
        ///   <c>true</c> if this instance has at least one item; otherwise, <c>false</c>.
        /// </value>
        public bool hasNext => this._used > 0;

        /// <summary>
        /// Gets the item at the front of the heap, but does not remove it.
        /// </summary>
        /// <returns>The item at the front of the heap.</returns>
        public T Peek()
        {
            if (this._used == 0)
                throw new InvalidOperationException("The Heap is empty, Peek cannot be called on an empty heap");
            return this._heap[0];
        }

        /// <summary>Clears the heap, removing all items.</summary>
        public void Clear()
        {
            Array.Clear((Array)this._heap, 0, this._used);
            this._used = 0;
        }

        /// <summary>Removes the specified item.</summary>
        /// <param name="item">The item.</param>
        /// <returns>The item that was removed or null if it was not found.</returns>
        public T Remove(T item)
        {
            int idx = Array.IndexOf<T>(this._heap, item, 0);
            return idx < 0 ? default(T) : this.Remove(idx);
        }

        /// <summary>
        /// Removes the first item that matches the specified predicate.
        /// </summary>
        /// <param name="predicate">The predicate.</param>
        /// <returns>The item that was removed or null if no item was not found.</returns>
        public T Remove(Func<T, bool> predicate)
        {
            int idx = -1;
            for (int index = 0; index < this._used; ++index)
            {
                if (predicate(this._heap[index]))
                {
                    idx = index;
                    break;
                }
            }
            return idx < 0 ? default(T) : this.Remove(idx);
        }

        /// <summary>Recreates the heap upwards from the specified item.</summary>
        /// <param name="item">The item.</param>
        public void ReheapifyUpFrom(T item)
        {
            int childIdx = Array.IndexOf<T>(this._heap, item, 1);
            if (childIdx < 1)
                return;
            this.ReheapifyUp(childIdx);
        }

        /// <summary>Recreates the heap downwards from the specified item.</summary>
        /// <param name="item">The item.</param>
        public void ReheapifyDownFrom(T item)
        {
            int currentIdx = Array.IndexOf<T>(this._heap, item, 0);
            if (currentIdx < 0)
                return;
            this.ReheapifyDown(currentIdx);
        }

        /// <summary>
        /// Recreates the heap downwards from the specified index.
        /// </summary>
        /// <param name="childIdx">Index of the child.</param>
        /// <exception cref="T:System.ArgumentOutOfRangeException">childIdx;Specified index is outside the valid range.</exception>
        public void ReheapifyDownFrom(int childIdx)
        {
            if (childIdx < 0 || childIdx >= this._heap.Length)
                throw new ArgumentOutOfRangeException(nameof(childIdx), "Specified index is outside the valid range.");
            this.ReheapifyDown(childIdx);
        }

        /// <summary>Resizes this instance.</summary>
        public void Resize()
        {
            T[] destinationArray = new T[this._heap.Length * 2];
            if (this._used > 0)
                Array.Copy((Array)this._heap, (Array)destinationArray, this._used);
            this._heap = destinationArray;
        }

        /// <summary>Enters an item in the heap.</summary>
        /// <param name="item">The item to add</param>
        protected void AddInternal(T item)
        {
            if (this._used == this._heap.Length)
                this.Resize();
            this._heap[this._used++] = item;
            this.ReheapifyUp(this._used - 1);
        }

        /// <summary>Removes the item at the front of the heap.</summary>
        /// <returns>The item at the front of the heap.</returns>
        protected T RemoveInternal() => this.Remove(0);

        private T Remove(int idx)
        {
            if (this._used == 0)
                throw new InvalidOperationException("The Heap is empty, Remove cannot be called on an empty heap");
            T obj = this._heap[idx];
            --this._used;
            this._heap[idx] = this._heap[this._used];
            this._heap[this._used] = default(T);
            this.ReheapifyDown(idx);
            return obj;
        }

        private void ReheapifyUp(int childIdx)
        {
            int index = (childIdx - 1) / 2;
            T x;
            for (x = this._heap[childIdx]; childIdx > 0 && this._comparer.Compare(x, this._heap[index]) > 0; index = (childIdx - 1) / 2)
            {
                this._heap[childIdx] = this._heap[index];
                childIdx = index;
            }
            this._heap[childIdx] = x;
        }

        private void ReheapifyDown(int currentIdx)
        {
            T x = this._heap[currentIdx];
            while (true)
            {
                int index1 = currentIdx * 2 + 1;
                if (index1 < this._used)
                {
                    int index2 = currentIdx * 2 + 2;
                    int index3 = index2 < this._used ? (this._comparer.Compare(this._heap[index1], this._heap[index2]) > 0 ? index1 : index2) : index1;
                    if (this._comparer.Compare(x, this._heap[index3]) < 0)
                    {
                        this._heap[currentIdx] = this._heap[index3];
                        currentIdx = index3;
                    }
                    else
                        break;
                }
                else
                    break;
            }
            this._heap[currentIdx] = x;
        }
    }
}